package linkedlist;
//模拟实现双向链表

//class Node{
//    //这里由于在同一个包中写了相同的类,就会报错
//    //可以通过改名,再创建一个包,或者将其作为内部类这三种方法来处理
//    //这里选择将其作为内部类来处理,内部类分为普通内部类,静态内部类,匿名内部类
//}
public class MyDLinkedList {
    //这里使用静态内部类,否则在后期使用时要加上this,特别不方便
    static class Node{
        public String val;
        public Node prev = null;
        public Node next = null;

        public Node(String val){
            this.val = val;
        }
    }

    //这里就不引入傀儡节点了
    private Node head = null;
    private Node tail = null;

    //实现头插
    public void addFirst(String val){
        Node newNode = new Node(val);
        if(head == null){
            head = newNode;
            tail = newNode;
        }else{
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    //实现尾插
    public void addLast(String val){
        Node newNode = new Node(val);
        if(head == null){
            head = newNode;
            tail = newNode;
        }else{
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    //按照下标进行插入操作
    public void add(int index,String val){
        //一定要先判断index的值是否越界了,要保持这个习惯
        int size = size();
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: " + index + ",Size: " + size);
        }
        if(index == 0){
            addFirst(val);
            return;
        }
        if(index == size()){
            addLast(val);
            return;
        }
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
        Node next = prev.next;
        Node newNode = new Node(val);
        prev.next = newNode;
        newNode.prev = prev;
        newNode.next = next;
        next.prev = newNode;

//        //注:如果不设置next节点的话,就需要这样写
//        prev.next.prev = newNode;
//        //先让后面的节点指向插入节点,再处理prev和插入节点的关系
//        //如果先处理prev和插入节点之间的关系,prev原来后面的节点就会丢失
//        //这样写从代码理解角度上看并不好
//        newNode.next = prev.next;
//        prev.next = newNode;
//        newNode.prev = prev;
    }

    //判断元素是否存在
    public boolean contains(String val){
        //遍历链表
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.val.equals(val)){
                return true;
            }
        }
        return false;
    }

    //查找元素,返回元素的下标
    public int indexOf(String val){
        int index = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.val.equals(val)){
                return index;
            }
            index++;
        }
        return -1;
    }

    //删除头部元素
    public void removeFirst(){
        if(head == null){
            return;
        }
        if(head.next == null){
            head = null;
            tail = null;//这里必须写上tail = null,因为写head = null只是把head的指向改为null,
            // 并没有改变newNode,tail指向的还是newNode,就会出错
            return;
        }
        head = head.next;
        head.prev = null;//如果链表中只有一个节点的话,那这句就出错了,next.prev = null
        //因此,还是需要在前面加一种情况
    }

    //删除尾部元素
    public void removeLast(){
        if(head == null){
            return;
        }
        if(head.next == null){
            head = null;
            tail = null;
        }
        tail = tail.prev;
        tail.next = null;
        //这时最后一个节点没有节点指向它,已经被释放掉了
    }

    //指定位置删除
    public void remove(int index){
        int size = size();
        //注意辨析,插入元素的时候可以等于size,删除的时候则不可以
        if(index < 0||index >= size){
            throw new IndexOutOfBoundsException("Size: " + size + "Index: " + index);
        }
        if(index == 0){
            removeFirst();
            return;
        }
        if(index == size - 1){
            removeLast();
            return;
        }
        //找到待删除的节点的前一个位置
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
//        prev.next = prev.next.next;
//        prev.next.prev = prev;
        //两种写法都可以,第二种写法更加清晰
        Node toRemove = prev.next;
        Node next = toRemove.next;
        prev.next = next;
        next.prev = prev;
    }

    //指定值删除
    public void remove(String val){
        if(head == null){
            return;
        }
        if(head.val.equals(val)){
            removeFirst();
            return;
        }
        if(tail.val.equals(val)){
            removeLast();
            return;
        }
        Node toRemove = head;
        for(;toRemove != null;toRemove = toRemove.next){
            if(toRemove.val.equals(val)){
                break;
            }
        }
        if(toRemove == null){
            return;
        }
        Node prev = toRemove.prev;
        Node next = toRemove.next;
        prev.next = next;
        next.prev = prev;
    }

    public int size(){
        int size = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            size++;
        }
        return size;
    }
    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(Node cur = head;cur != null;cur = cur.next){
            stringBuilder.append(cur.val);
            if(cur.next != null){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    public static void test1(){
        MyDLinkedList list = new MyDLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);
    }

    public static void test2(){
        MyDLinkedList list = new MyDLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        System.out.println(list);
        list.removeFirst();
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
    }

    public static void test3(){
        MyDLinkedList list = new MyDLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        list.add(2,"x");
        System.out.println(list);
        System.out.println(list.contains("a"));
        System.out.println(list.indexOf("d"));
    }
    public static void test4() {
        MyDLinkedList list = new MyDLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        list.remove(1);
        System.out.println(list);
    }

    public static void test5(){
        MyDLinkedList list = new MyDLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        list.remove("d");
        System.out.println(list);
    }

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
        test5();
    }
}
